
/**
 * @a https://leetcode.cn/problems/product-of-array-except-self/
 */

#include "common.h"


class Solution
{
public:
    vector<int> productExceptSelf(vector<int> &nums)
    {
        int sz = nums.size();
        vector<int> pre_product(sz);
        vector<int> sur_product(sz);

        pre_product[0] = sur_product[sz - 1] = 1;
        for(int i = 1; i < sz; ++i)
        {
            pre_product[i] = pre_product[i - 1] * nums[i - 1];
            sur_product[sz - i - 1] = sur_product[sz - i] * nums[sz - i];
        }

        vector<int> ans(sz);
        for(int i = 0; i < sz; ++i)
            ans[i] = pre_product[i]*sur_product[i];

        return ans;
    }
};